package Tree.binaryTree;


import java.util.*;

public class binaryTreeSolution03 {
    /**
     * 116. 填充每个节点的下一个右侧节点指针 - medium
     * @param root
     * @return
     */
    public IndexNode connect(IndexNode root) {
        if(root == null) {
            return null;
        }
        Queue<IndexNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int len = queue.size();
            IndexNode next = null;  //当前节点的下一个节点
            //每层从右往左遍历
            for (int i = len; i > 0; i--) {
                IndexNode cur = queue.poll();
                cur.next = next;
                next = cur;
                //下一次节点也是从右往左入队
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
            }

        }
        return root;
    }

    /**
     * 104. 二叉树的最大深度 - easy
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     * 其实就是树的深度/高度 可以用层序遍历，depth++的方式求解
     * @param root
     * @return
     */

    //从上往下，中序遍历求深度

    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()) {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            depth++;

        }
        return depth;
    }

    //还可以用递归来求解，就是求左右子树的最大高度再加1
    //从下往上 后序遍历求高度
    //后续遍历 把叶子节点的高度返回给父节点，然后返回给父节点，一直递归到根节点，返回高度。
    public int minDepth_1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //左右中
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        //如果左右子树有一个为空，则返回不为
        //中 -处理逻辑放最后
        return Math.max(leftDepth, rightDepth) + 1;
    }
    //还可以用前序遍历，+回溯，模拟求深度的过程
    public static int depth = 0;
    public int minDepth_2(TreeNode root) {
        if (root == null) {
            return depth;
        }
        getDepth(root, 1);
        return depth;
    }
    public void getDepth(TreeNode root, int depth) {
        if(root.left == null && root.right == null) {
            return;
        }
        if(root.left != null) {
            depth++;
            getDepth(root.left, depth);
            depth--; //回溯
        }
        if(root.right != null) {
            depth++;
            getDepth(root.right, depth);
            depth--;
        }
        return;
    }

    /**
     * 111. 二叉树的最小深度 - easy
     * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
     * 队列104 二叉树的最大深度题，这道题就是求二叉树左右子树的最小深度+1
     * 这道题的关键是搞清楚递归结束条件
     *
     * 叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
     * 当 root 节点左右孩子都为空时，返回 1
     * 当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
     * 当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值
     * @param root
     * @return
     */

    public int minDepth(TreeNode root){
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            depth++;
            TreeNode cur = null;
            for (int i = 0; i < size; i++) {
                cur = queue.poll();
                //如果当前节点的左右孩子都为空，说明这次层出现了叶子节点 直接返回最小深度
                if (cur.left == null && cur.right == null){
                    return depth;
                }
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return depth;
    }


    /**
     * 226. 翻转二叉树 - easy
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        transferTree(root);
        return root;
    }
    public void transferTree(TreeNode root){
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        transferTree(root.left);
        transferTree(root.right);
    }

    /**
     * 101. 对称二叉树 - easy
     * @param root
     * 递归
     * @return
     */
    //思路 因为我们要比较的是根节点的两个子树是否是相互翻转的，
    // 进而判断这个树是不是对称树，
    // 所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
//    本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
//
//    正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isReversal(root.left, root.right);
    }

    public boolean isReversal(TreeNode left, TreeNode right) {
        //添加递归终止条件
        //左右子树都空 -对称
        if (left == null && right == null) {
            return true;
        }
        //左右子树只有一个空 -不对称
        if (left == null || right == null) {
            return false;
        }
        //左右子树都不为空，但值不等
        if (left.val != right.val) {
            return false;
        }
        //添加递归逻辑
        //左右节点都不空，且值相等 -继续比较下一层
        //左子树的左节点和右子树的右节点是否相等 --外侧比较
        //和左子树的右节点和右子树的左节点是否相等  -- 内侧比较
        boolean outside = isReversal(left.left, right.right);
        boolean inside = isReversal(left.right, right.left);
        return outside && inside;
    }

    //用迭代法，非递归实现
    public boolean isSymmetric_1(TreeNode root) {
        if (root == null) {
            return true;
        }
        //用双端队列更好实现
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left == null && right == null) {
                return true;
            }
            if (left == null || right == null) {
                return false;
            }
            if (left.val != right.val) {
                return false;
            }
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }

    /**
     * 222. 完全二叉树的节点个数 -easy
     * @param root
     * @return
     */


    //1.递归法 后序遍历
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftCount = countNodes(root.left);
        int rightCount = countNodes(root.right);
        return leftCount + rightCount + 1;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        treeNode.left.left = new TreeNode(4);
        treeNode.left.right = new TreeNode(5);
        treeNode.right.left = new TreeNode(6);
        binaryTreeSolution03 binaryTreeSolution03 = new binaryTreeSolution03();
        int count= binaryTreeSolution03.countNodes(treeNode);
        System.out.println(count);
    }
    //2.层序遍历计算个数
    public int countNodes_1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 0;
        while (!queue.isEmpty()) {
            int len = queue.size();
            count += len;
            //该层出队，并添加下一层非空节点入队
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return count;
    }

}
